1. Field
One aspect of the subject matter relates to creation of scene acceleration structure for a 3-D scene to be rendered, and in a more particular aspect to creating or updating such an acceleration structure for use in rendering 2-D images from a 3-D scene description using ray tracing.
2. Related Art
Rendering photo-realistic 2-D images from 3-D scene descriptions with ray tracing is known in the computer graphics arts. Ray tracing usually involves obtaining a scene description composed of geometric shapes, which describe surfaces of structures in the scene. These geometric shapes are often called primitives, if they are the shapes that are a type of shape that is capable of being processed by the rendering system to be used; otherwise, the geometric shapes typically are processed in order to produce primitives based on the geometric shapes. For example, patches may be processed to produce triangular primitives.
The primitives can be associated with textures and other information that instructs a computer how light hitting that primitive should be affected by qualities of the primitive. Ray tracing can faithfully render complicated lighting, light transmission, reflection, refractions, and so on, because ray tracing can model the physical behavior of light interacting with elements of a scene.
A common operation in ray-tracing is to determine intersections between a ray and one or more primitives in the scene. An example of a primitive used in defining objects for ray tracing systems is a triangle composed of a collection of vertices located within a 3-D scene space; this description proceeds with this familiar example, but the use of triangular primitives is for clarity, and not by way of limitation.
A definition of a ray may consist of an origin, and a direction and a current clipping distance along the ray, which can be identified as the “t” for the ray. The current clipping distance identifies a current closest intersection detected for the ray, or in the absence of a detected intersection, that the ray has been tested for intersection for distances beyond that distance, and no intersection was found. When a ray completes intersection testing, a closest detected intersection can be returned, and information determined for that intersection, such as an identification of a primitive intersected by the ray.
Naively, these results can be determined for a given ray by iteratively testing every one of the triangles in the scene in order to identify the closest intersected triangle. While such a naive approach works acceptably for scenes with trivial numbers of triangles, this approach is intractable for complex scenes and for commercial products, where many millions, or even tens or hundreds of millions of rays may need to be tested for intersection with millions of triangles, for each frame to be rendered.
In order to accelerate such intersection testing, 3-D spatial acceleration structures are used. Such acceleration structures generally work by subdividing 3D space into different regions, where the regions can each bound a plurality of primitives. Then, each of the regions can be first tested for intersection, in order to determine whether the primitives in that region need to be tested individually or not. In some cases, acceleration structures can be hierarchical, such that multiple tests of different regions within the acceleration structure are performed in order to identify a relatively small set of primitives to be tested for intersection with a given ray.
For a properly assembled acceleration structure, a total number of ray intersection tests should be substantially less than having performed a ray-triangle test between every ray and every triangle in the scene.